/*
 * @lc app=leetcode id=81 lang=cpp
 *
 * [81] Search in Rotated Sorted Array II
 */
class Solution {
public:

    bool search(vector<int>& nums, int target) {
        int len = nums.size();
        int i = 0;
        int j = len-1;
        int mid;

        while (i <= j) {

            while (i<j && nums[j-1] == nums[j])
                j--;
            while (i<j && nums[i+1] == nums[i])
                i++;

            mid = (i+j)/2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[mid] <= nums[j]) {
                if (target > nums[mid] && target <= nums[j]) {
                    i = mid+1;
                } else {
                    j = mid-1;
                }
            } else {
                if (target >= nums[i] && target < nums[mid]) {
                    j = mid-1;
                } else {
                    i = mid+1;
                }
            }
        }
        return false;
    }
};

